package leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点总数在范围 [0, 5000] 内
 * -1000 <= Node.val <= 1000
 * -1000 <= targetSum <= 1000
 */
public class LeetCode113_PathSum2 {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> r = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        resolve(r, path, root, targetSum);
        return r;
    }

    public void resolve(List<List<Integer>> r, List<Integer> curPath, TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        if (isLeaf(root)) {
            curPath.add(root.val);
            if (isTargetSum(curPath, targetSum)) {
                r.add(copyPath(curPath));
            }
            return;
        }
        curPath.add(root.val);

        if (root.left != null) {
            resolve(r, curPath, root.left, targetSum);
            curPath.remove(curPath.size() - 1);
        }
        if (root.right != null) {
            resolve(r, curPath, root.right, targetSum);
            curPath.remove(curPath.size() - 1);
        }
    }

    public List<Integer> copyPath(List<Integer> curPath) {
        List<Integer> copyPath = new ArrayList<>();
        for (Integer x : curPath) {
            copyPath.add(x);
        }
        return copyPath;
    }

    public boolean isTargetSum(List<Integer> curPath, int targetSum) {
        int s = 0;
        for (Integer x : curPath) {
            s += x;
        }
        return s == targetSum;
    }

    public boolean isLeaf(TreeNode root) {
        return root.left == null && root.right == null;
    }
}
